package leetcode.code0032;

public class Solution extends Solution32 {

	@Override
	public int longestValidParentheses(String s) {
		if (s.length() == 0)
			return 0;
		char[] chars = s.toCharArray();
		int match = 0;// 模拟栈，匹配左右括号。出现左括号+1，出现右括号-1
		int max = 0;// 最长有效配对括号
		int count = 0;// 记录当前连续有效配对括号数量
		int p = 0;// 一直往前走
		int len = chars.length;
		char[] stack = new char[len];
		int ps = -1;
		while (p < len) {
			if (chars[p] == '(') {
				match++;
				stack[++ps] = '(';
			} else if (chars[p] == ')') {
				match--;
				stack[++ps] = ')';
				if (match >= 0) {// 成功消除一对儿
					count += 2;// 两个成对，有效成对儿数量+2
				} else if (match < 0) {// 有多余的右括号，配不上对儿，结算答案
					max = Math.max(max, count);
					count = 0;// 重新数数
					match = 0;// 重新匹配
					ps = -1;
				}
			}
			p++;
		}
		match = 0;
		count = 0;
		while (ps >= 0) {
			if (stack[ps] == ')') {
				match++;
			} else if (stack[ps] == '(') {
				match--;
				if (match >= 0) {// 成功消除一对儿
					count += 2;// 两个成对，有效成对儿数量+2
				} else if (match < 0) {// 有多余的右括号，配不上对儿，结算答案
					max = Math.max(max, count);
					count = 0;// 重新数数
					match = 0;// 重新匹配
				}
			}
			ps--;
		}
		max = Math.max(max, count);// ps跳出循环，结算最后一个count
		return max;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		int r = 0;
		r = so.longestValidParentheses(")())(((())(()())))");
		System.out.println(r);
//		r = so.longestValidParentheses("()(()");
//		System.out.println(r);
//		r = so.longestValidParentheses("(()(()");
//		System.out.println(r);
	}

}
